DROPS

Document

DOI: 10.4230/LIPIcs.IPEC.2018.4

Multivariate Analysis of Orthogonal Range Searching and Graph Distances

Authors: Karl Bringmann, Thore Husfeldt, and Måns Magnusson

Published in: LIPIcs, Volume 115, 13th International Symposium on Parameterized and Exact Computation (IPEC 2018)

Abstract

We show that the eccentricities, diameter, radius, and Wiener index of an undirected n-vertex graph with nonnegative edge lengths can be computed in time O(n * binom{k+ceil[log n]}{k} * 2^k k^2 log n), where k is the treewidth of the graph. For every epsilon>0, this bound is n^{1+epsilon}exp O(k), which matches a hardness result of Abboud, Vassilevska Williams, and Wang (SODA 2015) and closes an open problem in the multivariate analysis of polynomial-time computation. To this end, we show that the analysis of an algorithm of Cabello and Knauer (Comp. Geom., 2009) in the regime of non-constant treewidth can be improved by revisiting the analysis of orthogonal range searching, improving bounds of the form log^d n to binom{d+ceil[log n]}{d}, as originally observed by Monier (J. Alg. 1980). We also investigate the parameterization by vertex cover number.

Cite as

Karl Bringmann, Thore Husfeldt, and Måns Magnusson. Multivariate Analysis of Orthogonal Range Searching and Graph Distances. In 13th International Symposium on Parameterized and Exact Computation (IPEC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 115, pp. 4:1-4:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{bringmann_et_al:LIPIcs.IPEC.2018.4,
  author =	{Bringmann, Karl and Husfeldt, Thore and Magnusson, M\r{a}ns},
  title =	{{Multivariate Analysis of Orthogonal Range Searching and Graph Distances}},
  booktitle =	{13th International Symposium on Parameterized and Exact Computation (IPEC 2018)},
  pages =	{4:1--4:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-084-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{115},
  editor =	{Paul, Christophe and Pilipczuk, Michal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2018.4},
  URN =		{urn:nbn:de:0030-drops-102050},
  doi =		{10.4230/LIPIcs.IPEC.2018.4},
  annote =	{Keywords: Diameter, radius, Wiener index, orthogonal range searching, treewidth, vertex cover number}
}

Search Results

Documents authored by Magnusson, Måns

Multivariate Analysis of Orthogonal Range Searching and Graph Distances

Abstract

Cite as

Thanks for your feedback!

Could not send message